Sắp xếp trộn
Sắp xếp trộn

Sắp xếp trộn

Trong khoa học máy tính, sắp xếp trộn (merge sort) là một thuật toán sắp xếp để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, v.d. luồng tập tin) theo một trật tự nào đó. Nó được xếp vào thể loại sắp xếp so sánh. Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị do John von Neumann đưa ra lần đầu năm 1945[1]. Một thuật toán chi tiết được Goldstine và Neumann đưa ra năm 1948.[2]

Sắp xếp trộn

Độ phức tạp không gian trường hợp tệ nhất Cần vùng nhớ trung gian khác nhau tùy loại
Cấu trúc dữ liệu Khác nhau
Phân loại Giải thuật sắp xếp
Tối ưu Thỉnh thoảng
Hiệu suất trường hợp tệ nhất Trung bình O ( n log ⁡ n ) {\displaystyle O(n\log n)}